//使得arr[s]到arr[m]成为一个大顶堆
#include <math.h>
#include <vector>
using namespace std;

void HeapAdjust(int *arr, int s, int m) {
    int temp, j;
    temp = arr[s];
    //循环遍历其结点的孩子，完全二叉树，当前节点为s,其左子树的序号一定是2*s;右孩子一定是2*s+1，孩子以2的位数序号增加;
    for (j = 2 * s; j <= m; j *= 2) {
        if (j < m&&arr[j] < arr[j + 1])
            ++j; /* j为关键字中较大的记录的下标*/
        if (temp >= arr[j])
            break;   /*rc应插入在位置s上*/
        arr[s] = arr[j];
        s = j;
    }
    arr[s] = temp; //插入
}

void HeapSort(int *arr, int len) {
    int i;
    /*构建大顶堆，遍历的都是有孩子的结点*/
    //大顶堆是从下往上、从右到左都是递减的
    for (int i = len / 2; i > 0; i--) {
        HeapAdjust(arr, i, len);
    }
    for (int i = len; i > 0; i--) {
//将堆顶记录和当前未经排序子序列的最后一个记录交换
        swap(arr[0], arr[i]);
//将arr[0]到arr[i-1]重新调整为大顶堆;
        HeapAdjust(arr, 0, i - 1);
    }
}

